class Node {
    constructor() {
        this.children = new Array(26).fill(null)
        this.isWord = false
    }
}

var WordDictionary = function() {
    this.root = new Node()
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
    let curr = this.root
    for (const c of word) {
        const index = c.charCodeAt() - 'a'.charCodeAt()
        if (!curr.children[index]) {
            curr.children[index] = new Node()
        }
        curr = curr.children[index]
    }
    curr.isWord = true
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {

    const dfs = (node, index) => {
        if (index == word.length) return node.isWord;
        const c = word[index]
        if (c != '.') {
            const i = c.charCodeAt() - 'a'.charCodeAt()
            if (!node.children[i]) return false;
            return dfs(node.children[i], index + 1)
        } else {
            for (const child of node.children) {
                if (child && dfs(child, index + 1)) return true;
            }
            return false;
        }
    }

    return dfs(this.root, 0)
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */